package problem147_Insertion_Sort_List;

import problem82_Remove_Duplicates_from_Sorted_List2.ListNode;

public class Solution {
	public ListNode insertionSortList(ListNode head) {
		if (head == null || head.next == null)
			return head;

		// We started a new list here, not the original one
		ListNode dummy = new ListNode(0);
		ListNode curt = head, prev = dummy, next = head;
		while (curt != null) {
			next = curt.next;

			while (prev.next != null && prev.next.val < curt.val) {
				prev = prev.next;
			}

			curt.next = prev.next;
			prev.next = curt;
			curt = next;
			prev = dummy;
		}

		return dummy.next;
	}

	public static void main(String[] args) {
		ListNode node = new ListNode(2);
		node.next = new ListNode(1);
		System.out.println(new Solution().insertionSortList(node).val);
	}
}
